package com.cqs.leetcode;


import java.util.*;

/**
 * Created by cqs on 2018/3/31.
 */
public class BinaryTreeInorderTraversal {
    private TreeNode root;

    //
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node != null || !stack.empty()) {//终止条件
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            TreeNode pop = stack.pop();
            list.add(pop.val);
            node = pop.right;
        }
        return list;
    }


//    public static void main(String[] args) {
//        BinaryTreeInorderTraversal b = new BinaryTreeInorderTraversal();
//        Integer[] nodes = {1, null, 2, null, null, 3};
//        b.root = TreeUtils.buildTree(nodes);
//        List<Integer> list = b.inorderTraversal(b.root);
//        System.out.println(list);
//    }
}
